class Solution {
public:
    int reversePairs(vector<int>& record) {
        MergeSort(record, record.size());

        return _cnt;
    }

    void MergeSort(vector<int>& nums, int n)
    {
        vector<int> tmp(n);
        _cnt = _MergeSort(nums, 0, n - 1, tmp);
    }

    // 归并排序子程序--升序
    int _MergeSort(vector<int>& nums, int left, int right, vector<int>& tmp)
    {
        if(left >= right) return 0;

        int ret = 0;    // 统计逆序对个数

        int mid = (right - left) / 2 + left;
        // 根据 mid 划分成两个序列：[left, mid] [mid + 1, right]

        // 左边逆序对个数 + 排序 + 右边逆序对个数 + 排序
        ret += _MergeSort(nums, left, mid, tmp);
        ret += _MergeSort(nums, mid + 1, right, tmp);
        
        // 一左一右的个数
        // 合并[left, mid] [mid + 1, right]
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = begin1;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(nums[begin1] <= nums[begin2])
            {
                tmp[index++] = nums[begin1++];  // 排序
            }
            else
            {
                ret += mid - begin1 + 1;
                tmp[index++] = nums[begin2++];
            }
        }

        // 可能存在第一个序列中的数据没有全部放到 tmp 中
        while(begin1 <= end1)
            tmp[index++] = nums[begin1++];

        // 可能存在第二个序列中的数据没有全部放到 tmp 中
        while(begin2 <= end2)
            tmp[index++] = nums[begin2++];

        // 将 tmp 中的元素挪回 nums 数组
        for(int i = left; i <= right; ++i)
            nums[i] = tmp[i];

        return ret;
    }

private:
    int _cnt = 0;   // 统计逆序对数量
};
//####################################################################
class Solution {
public:
    int reversePairs(vector<int>& record) {
        MergeSort(record, record.size());

        return _cnt;
    }

    void MergeSort(vector<int>& nums, int n)
    {
        vector<int> tmp(n);
        _cnt = _MergeSort(nums, 0, n - 1, tmp);
    }

    // 归并排序子程序--降序
    int _MergeSort(vector<int>& nums, int left, int right, vector<int>& tmp)
    {
        if(left >= right) return 0;

        int ret = 0;    // 统计逆序对个数

        int mid = (right - left) / 2 + left;
        // 根据 mid 划分成两个序列：[left, mid] [mid + 1, right]

        // 左边逆序对个数 + 排序 + 右边逆序对个数 + 排序
        ret += _MergeSort(nums, left, mid, tmp);
        ret += _MergeSort(nums, mid + 1, right, tmp);
        
        // 一左一右的个数
        // 合并[left, mid] [mid + 1, right]
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = begin1;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(nums[begin1] <= nums[begin2])
            {
                tmp[index++] = nums[begin2 ++];  // 排序
            }
            else
            {
                ret += right - begin2 + 1;
                tmp[index++] = nums[begin1++];
            }
        }

        // 可能存在第一个序列中的数据没有全部放到 tmp 中
        while(begin1 <= end1)
            tmp[index++] = nums[begin1++];

        // 可能存在第二个序列中的数据没有全部放到 tmp 中
        while(begin2 <= end2)
            tmp[index++] = nums[begin2++];

        // 将 tmp 中的元素挪回 nums 数组
        for(int i = left; i <= right; ++i)
            nums[i] = tmp[i];

        return ret;
    }

private:
    int _cnt = 0;   // 统计逆序对数量
};